#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>

void Swap(int* x, int* y)
{
	int tmp = *x;
	*x = *y;
	*y = tmp;
}

//快速排序  Hoare版本
int _QuickSort(int* arr, int left, int right)
{
	int keyi = left;
	left++;
	while (left <= right)
	{
		//right 从右往左走找比基准值要小的数据
		while (left <= right && arr[right] > arr[keyi])
		{
			right--;
		}
		//left 从左往右走找比基准值要大的数据
		while (left <= right && arr[left] < arr[keyi])
		{
			left++;
		}

		//left和right交换
		if (left <= right)
		{
			Swap(&arr[left++], &arr[right--]);
			//循环最后left++ right-- 判断是否进入下一次循环并继续执行
		}
	}
	Swap(&arr[keyi], &arr[right]);
	return right--; //返回基准值的下标
}

void QuickSort(int* arr, int left, int right)
{
	if (left >= right)
	{
		return;
	}
	//找基准值
	int keyi = _QuickSort(arr, left, right);
	//二分
	QuickSort(arr, left, keyi - 1);
	QuickSort(arr, keyi + 1, right);
}

int main()
{
	int arr[10] = { 2,4,1,9,3,6,5,0,7,8 };
	int len = sizeof(arr) / sizeof(arr[0]);
	QuickSort(arr, 0, len - 1);
	for (int i = 0; i < len - 1; i++)
	{
		printf("%d ", arr[i]);
	}
	return 0;
}